
package com.code.test.first.greedy;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.md
 *
 * 给出一个区间的集合，请合并所有重叠的区间。
 *
 * 示例 1:
 *
 * 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2:
 *
 * 输入: intervals = [[1,4],[4,5]]
 * 输出: [[1,5]]
 * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 * 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
 */
public class Code56 {

    public static void main(String[] args) {
        int[][] interval = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        interval = merge2(interval);
        System.out.println(Arrays.deepToString(interval));
    }


    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                //相同元素，第二维升序
                return a[1] - b[1];
            }
            //第一维升序
            return a[0] - b[0];
        });

        List<int[]> ret = new LinkedList<>();

        int start = intervals[0][0];
        //区间右边界
        int rightmostRightBound = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > rightmostRightBound) {
                //如果当前左边界大于前一个的右边界
                //也就是两个没有重叠
                ret.add(new int[]{start, rightmostRightBound});
                start = intervals[i][0];
                rightmostRightBound = intervals[i][1];
            } else {
                //有重叠的话，则把右边界置为最大的那一个
                /**
                 * 前提是已经排过序
                 * 然后每次迭代都更新为最大，知道没有重叠，将最后的左右区间都扔到结果
                 */
                rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
            }
        }
        //最后一个是还没有放进结果里
        ret.add(new int[]{start, rightmostRightBound});

        return ret.toArray(new int[ret.size()][]);
    }

    public static int[][] merge2(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                //相同元素，第二维升序
                return a[1] - b[1];
            }
            //第一维升序
            return a[0] - b[0];
        });

        LinkedList<int[]> ret = new LinkedList<>();
        //先把第一个元素放进去
        ret.add(intervals[0]);

        /**
         * 每次都跟集合里的最后一个元素比较，有重叠就剔除，再放进去
         */
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < ret.getLast()[1]) {
                //当前左边界小于前一个元素右边界，说明没有重叠
                int start = ret.getLast()[0];
                int end = Math.max(ret.getLast()[1], intervals[i][1]);
                ret.removeLast();
                ret.add(new int[]{start, end});
            } else {
                ret.add(intervals[i]);
            }
        }

        return ret.toArray(new int[ret.size()][]);
    }

}
